package 栈;
import java.util.*;
/**
 * 该类用于检查字符串中的括号是否有效。
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
public class isValid {
    /**
     * 检查字符串中的括号是否有效。
     * 该方法使用栈来匹配括号，确保每个括号都能正确闭合。
     * @param s 输入的字符串
     * @return 如果括号有效则返回 true，否则返回 false
     */
    public boolean isVal(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>(); // 创建一个栈来存储括号
        for(char c : s.toCharArray()) { // 遍历字符串中的每个字符
            if(c == '(' || c == '[' || c == '{') { // 如果是左括号，入栈
                stack.push(c);
            } else { // 如果是右括号
                if(stack.isEmpty()) { // 如果栈为空，说明没有匹配的左括号
                    return false;
                } else if(c == ')' && stack.peek() == '(') { // 如果右括号与栈顶的左括号匹配
                    stack.pop(); // 弹出栈顶的左括号
                } else if(c == ']' && stack.peek() == '[') { // 如果右括号与栈顶的左括号匹配
                    stack.pop(); // 弹出栈顶的左括号
                } else if(c == '}' && stack.peek() == '{') { // 如果右括号与栈顶的左括号匹配
                    stack.pop(); // 弹出栈顶的左括号
                } else { // 如果不匹配，返回 false
                    return false;
                }
            }
        }
        if(!stack.isEmpty()) return false; // 如果栈不为空，说明有未匹配的左括号
        return true; // 所有括号都匹配，返回 true
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取字符串，并输出括号是否有效。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String s = sc.nextLine(); // 读取输入的字符串
        isValid iv = new isValid(); // 创建对象
        System.out.println(iv.isVal(s)); // 输出括号是否有效
        sc.close(); // 关闭扫描器
    }
}
